package com.hanxiaozhang.sort;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈堆排序〉
 *
 * @author hanxinghua
 * @create 2021/9/14
 * @since 1.0.0
 */
public class HeapSort {


    public static void main(String[] args) {

        int[] array = {2, 3, 1, 6, 8, 3};
        heapSort1(array);
        System.out.println(Arrays.toString(array));

    }


    /**
     *  优势：堆排序额外空间复杂度O(1)
     *
     * 从上到下的方法，时间复杂度为O(N*logN)
     *
     * @param array
     */
    public static void heapSort1(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        // 整体：O(N*logN)
        // O(N)
        for (int i = 0; i < array.length; i++) {
            // O(logN)
            heapInsert(array, i);
        }
        int heapSize = array.length;
        swap(array, 0, --heapSize);
        // 整体：O(N*logN)
        // O(N)
        while (heapSize > 0) {
            // O(logN)
            heapify(array, 0, heapSize);
            // O(1)
            swap(array, 0, --heapSize);
        }
    }

    /**
     * 优势：堆排序额外空间复杂度O(1)
     *
     * 从下到上的方法，时间复杂度为O(N)
     *
     * @param array
     */
    public static void heapSort2(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        // 整体：O(N)
        for (int i = array.length - 1; i >= 0; i--) {
            heapify(array, i, array.length);
        }
        int heapSize = array.length;
        swap(array, 0, --heapSize);
        // 整体：O(N*logN)
        // O(N)
        while (heapSize > 0) {
            // O(logN)
            heapify(array, 0, heapSize);
            // O(1)
            swap(array, 0, --heapSize);
        }
    }

    /**
     * 加入元素到堆中
     *
     * @param array
     * @param index
     */
    public static void heapInsert(int[] array, int index) {
        while (array[index] > array[(index - 1) / 2]) {
            swap(array, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     *
     * @param array
     * @param index
     * @param heapSize
     */
    public static void heapify(int[] array, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && array[left + 1] > array[left] ? left + 1 : left;
            largest = array[largest] > array[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(array, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


}
